This invention relates to pattern recognition. In particular, the invention relates to the recognition of image contours and line-drawn graphics using Fourier descriptors. Computer-aided recognition of image contours or line-drawn patterns finds application wherever it is useful to automatically interpret visual information. Representative examples include handwriting recognition, military target acquisition, automotive collision avoidance systems, and personal identification systems for security. Typically, digital information about line-drawn patterns or the boundary curves of an object is converted into a set of features that are analyzed to produce a recognition result.
A general principle known to those of skill in the recognition art is that a small representative set of mutually independent features provides the most effective recognition. Another motivation for minimizing the number of features used to describe an object to be recognized is compression for storage. This is particularly important when recognition is to be deferred as in handwriting recognition applications used in conjunction with pen-based computers and personal digital assistants (PDAs). In these systems, the written characters are stored in compressed form prior to deferred recognition.
The Fourier descriptors of contours represent one type of feature set usable for recognition. The usual process of obtaining the Fourier descriptors can be divided into two steps. First, the contours, i.e. the boundary curves, of the object are extracted and traced to develop a certain description of these boundary curves as a function of arclength. One useful example of this function is a discrete natural parametric representation of each boundary curve, i.e., the sequence of coordinates of equidistantly spaced points along the curve. This representation is then converted into a set of Fourier coefficients, e.g., by use of the Discrete Fourier Transform, to obtain the set of Fourier descriptors. Second, the set of Fourier descriptors so-derived, is processed to obtain invariance with respect to scale, translation and rotation of the object, and to position of the point used to start the tracing. The resulting processed Fourier descriptor set is then available as a feature set for further recognition processing.
Recognition techniques that take advantage of Fourier descriptors derived from the natural parametric representation of the boundary curve were described, in particular, by V. G. Polyakov et al., The Line-Tracing Scanners, "Energia" publishing house, Moscow, 1968 (in Russian) and by G. H. Granlund et al., Fourier Preprocessing for Hand Print Character Recognition, IEEE Trans. Computers, vol. C-21, pp. 269-281, 1972. The contents of these references are herein incorporated by reference.
Several recognition techniques using various types of Fourier descriptors were reviewed by E. Persoon et al., Shape Discrimination Using Fourier Descriptors, IEEE Trans. on Systems, Man, and Cybernetics, vol. SMC-7, No.3, pp. 170-179, 1977. Fourier descriptors derived from the natural parametric representation were shown by E. Persoon et al. to have some important advantages relative to ones derived from other descriptions, such as curvature or modified tangent angle taken as functions of the boundary arclength.
E. Persoon et al. further taught obtaining Fourier descriptors for "line patterns", i.e. for non-closed curves. The underlying natural parametric representation for a line pattern is obtained by tracing the line pattern forward once from one end to the other end and then retracing back to the beginning. This representation can be interpreted as an even continuation of the parametric representation obtained by the forward part of tracing. The result is a cosine-like transform achieved by application of the Discrete Fourier Transform, providing Fourier descriptors in the form of "Cosine descriptors."
Unfortunately, Fourier descriptors derived according to these prior art techniques are not mutually independent, and include a degree of redundancy. The prior art techniques require a relatively large set of Fourier descriptors to capture distinctions between objects to be recognized. This however conflicts with the previously stated principle of recognition that calls for small mutually independent feature sets. Furthermore, these large feature sets are unsuitable for intermediate storage in applications which require deferred recognition.
What is needed is an effective pattern recognition technique based on Fourier descriptors of curves and/or line patterns of an object to be recognized. The Fourier descriptors should be mutually independent and non-redundant, making them suitable for both effective recognition and compression.